package com.ujs.listnode.code.removeNthFromEnd;

import com.ujs.listnode.code.ListNode;
import com.ujs.listnode.code.NodeInit;

import java.util.List;

/**
 * @author zhangshihao
 * @create 2023-10-09 20:22
 */
public class RemoveNthFromEnd {
    public static void main(String[] args) {
        ListNode head = NodeInit.getNode();  // 1 2 3 4 5 6
        ListNode listNode = removeNthFromEnd(head, 6);
        while (listNode != null) {
            System.out.print(listNode.getVal() + " ");
            listNode = listNode.getNext();
        }
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 先翻转该链表，这样可以把倒数的数字，转为正数
        ListNode pre = null, cur = head;
        int count = 0; // 统计链表的长度
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            count++;
        }
        // 删除链表中的第n个元素
        head = pre;
        ListNode dumyHead = new ListNode(-1, head);
        pre = dumyHead;
        cur = head;
        int index = 1;
        while (cur != null) {
            if (index == n) {
                // 需要删除
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
            index++;
        }
        // 先翻转该链表，这样可以把倒数的数字，转为正数
        pre = null;
        cur = dumyHead.next;
        count = 0; // 统计链表的长度
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            count++;
        }
        return pre;
    }
}
